import "errors"

/*
 * @lc app=leetcode.cn id=445 lang=golang
 *
 * [445] 两数相加 II
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

type Stack struct {
	data []int
}

func (s *Stack) Pop() int {
	tmp := s.data[len(s.data)-1]
	s.data = s.data[:len(s.data)-1]
	return tmp
}

func (s *Stack) Push(e int) bool {
	s.data = append(s.data, e)
	return true
}

func (s *Stack) Peek() (int, error) {
	if s.Empty() {
		return 0, errors.New("empty stack")
	} else {
		return s.data[len(s.data)-1], nil
	}
}

func (s *Stack) Empty() bool {
	if len(s.data) == 0 {
		return true
	} else {
		return false
	}
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	if l1 == nil {
		return l2
	}

	if l2 == nil {
		return l1
	}

	s1, s2 := &Stack{}, &Stack{}
	for l1 != nil {
		s1.Push(l1.Val)
		l1 = l1.Next
	}
	for l2 != nil {
		s2.Push(l2.Val)
		l2 = l2.Next
	}

	carry := 0
	dummyNode := &ListNode{}
	//current := dummyNode
	for carry != 0 || (!s1.Empty()) || (!s2.Empty()) {
		sum := carry
		if !s1.Empty() {
			sum += s1.Pop()
		}

		if !s2.Empty() {
			sum += s2.Pop()
		}

		//头插法插入链表
		tmp := &ListNode{Val: sum % 10, Next: nil}
		tmp.Next = dummyNode.Next
		dummyNode.Next = tmp
		//current.Next = &ListNode{Val: sum % 10, Next: nil}
		//current = current.Next
		carry = sum / 10
	}

	return dummyNode.Next
}

// @lc code=end

